1. Field of the Invention
The present invention relates generally to the interlacing of progressive scan video data and particularly to the use of object motion estimation to interlace progressive scan video data.
2. Description of the Background Art
A device for displaying a video signal, such as for instance a television set or a computer monitor, typically consists of an array of pixel locations, often arranged on a rectangular grid. The device colors various pixel locations to display snapshot images, and these colors can change rapidly over time as a succession of images is transmitted. This rapid succession of images appears as a continuous moving picture to a human observer. The information contained in the video signal is relayed to these pixel locations on the display device in some temporal order so as to create the best video quality possible. For instance, in the case of television, a cathode ray tube is used to fire electrons at particular pixel locations on an excitable phosphorescent surface. The electron beam is very rapidly deflected to send the relevant information to each pixel location during a sweep through all pixel locations so that the entire display is covered in a fraction of one second. The color of the excited pixel locations persists for a finite period of time as the ray completes each scan.
During the development of television technology, a number of canonical choices were made regarding the temporal order in which display pixels receive their electrical impulses. The electron beam canonically traverses the rectangular array in raster-scan order, meaning it crosses each row from left to right and it proceeds top to bottom through all rows. In the 1930s and '40s as television matured, the demand for higher display resolution outpaced the electrical machinery of the day. Since the electron beam of a cathode ray tube could not be deflected fast enough to fill an entire higher resolution display in the desired time increment without greatly increasing costs, the decision was made to skip every other row in the array and thus to fill only half of it in one raster scan, then return to the top and perform a second raster scan for the previously omitted rows. This display method is commonly referred to as interlacing a video sequence.
In an interlaced display, each resultant image of a single one of the two interlaced scans is referred to as a “field” (as opposed to the entire “frame” presented during progressive scan). By convention, the two fields that together fill the pixel array are referred to herein as an odd field and an even field, representing the odd numbered rows and the even numbered rows, respectively. FIG. 1 illustrates the division of an image into an odd field and an even field. Full frame 100 consists of a lightly shaded background and two overlapping gray rectangles. The division of the frame into rows is depicted, and the width of the rows is enlarged beyond typical pixel width for illustrative purposes. Odd field 110 contains only the image data contained in the odd rows, while even field 120 contains only the image data contained in the even rows. If overlaid, the odd field 110 and the even field 120 will reconstitute the full frame 100.
Since the second scan occurs later in time, the pixels hit in the second scan actually display an image that occurs slightly later in time than the image depicted by the first scan. In the case of a video sequence containing motion, this fact implies that the later of two fields will actually sometimes display objects in different positions than in the previous field.
As electronic equipment used for television matured in later decades, the ability to scan through the entire array of pixels at each time increment developed. The term progressive scan refers to the process of filling the entire array of pixels to create a complete video frame with each pass of the electron beam. Modern computer monitors, as one prototypical example, use progressive scan technology.
An interlaced signal contains half of the information for each field that is contained in a single frame of a progressive signal. For this reason, quality comparisons between the two presentation formats are typically made between a progressive signal and an interlaced signal with twice as many fields per second. For instance, a progressive video containing 30 frames per second (standard in the U.S.) corresponds to an interlaced video containing 60 fields per second. In such comparisons, interlaced signals have the advantage of providing smoother motion since there are more incremental movements per second, but they typically suffer from some blurry artifacts caused by the offset fields that do not appear in a progressive video. Of course 60 frames per second of progressive video (at the same individual image quality) will look better than 60 fields per second, but bandwidth constraints render such a progressive frame rate impractical for many purposes.
The presence of these two display technologies can present compatibility difficulties. For instance, most video sequences prepared for television display are recorded in an interlaced format, which is not suited for display on a progressive scan device. However, a progressive scan format is desirable or necessary for a number of purposes, including display on progressive scan devices, video processing, and certain schemes for video compression. The need often arises to display a video sequence that is recorded in progressive scan on an interlaced display device, so converting between the two standards for video display is important. The process of converting a progressive scan video sequence to an interlaced video sequence is herein referred to as interlacing.
The primary known methods for interlacing a progressive sequence consist of line dropping and frame separation. Line dropping is the process of dropping even or odd lines from alternate frames in a progressive sequence so that only odd or even lines remain. For instance, if a 60 frame per second progressive sequence is to be converted into a 60 field per second interlaced sequence, then line dropping is a suitable option. Half of the lines are dropped from each frame so that only a single field remains, and this is done so that fields alternate between odd and even. But when the number of frames per second in the progressive sequence is less than the desired number of fields per second, line dropping is no longer useful.
FIG. 2 is an illustration of interlacing by line dropping. Frames 200 and 202 are two consecutive frames from a progressive video sequence depicting the rightward motion of a gray disk. Field 204 contains only the odd lines from frame 200 (so the even lines have been dropped), while field 206 contains only the even lines from frame 202 (so the odd lines have been dropped). Fields 204 and 206 represent consecutive fields from the interlaced sequence.
Frame separation refers to the process of subdividing each frame into two component fields (odd lines and even lines) and staggering the fields temporally to generate an interlaced format. An implementation of interlacing by frame separation is discussed, for example, in U.S. Pat. No. 4,298,888 to Joseph H. Colles et al. This method applies most directly when the desired interlaced field rate is twice the progressive frame rate, for instance when a 30 frame per second progressive sequence is converted to a 60 field per second interlaced sequence. However, because pairs of fields, which are displayed at slightly different times, are extracted from the same moment in time depicted in an original frame, no motion is represented between these fields. Hence this method fails to achieve the advantage of smoother motion that is associated with an interlaced format. Instead, motion only occurs between every other pair of fields, which can result in a somewhat jerky visual effect.
FIG. 3 is an illustration of interlacing by frame separation. Frames 200 and 202 are the same consecutive frames from a progressive video sequence shown in FIG. 2. Field 304 contains the odd lines from frame 200, while field 306 contains the even lines from frame 200. Frame 202 is separated into its own pair of even and odd fields (not depicted). Thus the interlaced sequence contains two fields separated from each frame of the progressive sequence.